package com.zjj.algorithm.learning.leetcode.linkedlist;

/**
 * 中档题
 * 19. 删除链表的倒数第 N 个结点
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 * 输入：head = [1,2,3,4,5], n = 2
 * 输出：[1,2,3,5]
 * @author zjj_admin
 * @date 2022/11/2 14:14
 */
public class DeleteLastNode {


    public static void main(String[] args) {

    }


    /**
     * 删除  此方法有问题
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd1(ListNode head, int n) {
        if(head.next == null){
            return null;
        }
        //定义一个初始，指向第一个节点
        ListNode temp = head;
        //首先将temp指向第整数第 n 个节点
        for (int i = 0; i <= n - 1; i++) {
            temp = temp.next;
        }
        ListNode temp2 = head;
        while (true){
            if(temp.next == null){
                break;
            }
            temp = temp.next;
            temp2 = temp2.next;
        }
        temp2.next = temp2.next.next;
        return head;
    }


    /**
     * 设置虚拟节点
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd2(ListNode head, int n) {
        // 虚拟头节点
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        // 要删除倒数第 n 个节点，那我们需要找到倒数第 n + 1 个节点
        ListNode node = findFromEnd(dummy, n + 1);
        // 节点的删除操作
        node.next = node.next.next;
        return dummy.next;

    }

    ListNode findFromEnd(ListNode head, int k) {
        ListNode p1 = head;
        // p1 先走 k 步
        for(int i = 0; i < k; i++) {
            p1 = p1.next;
        }
        // p2 登场，然后它俩以相同的速度走
        ListNode p2 = head;
        while(p1 != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        // 此时的 p2 刚好走到倒数第 n 个节点的位置
        return p2;
    }


}
